#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2021/01/11
# @Author   :Changshu
# @File     :Exercise_665.py

# 665. 非递减数列

# 给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
#
# 我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。


class Solution:
	'''法一：暴力解法，让每个值都消失一次，如果存在一次消失后的序列是非递减的，那么就返回true
		果然超时

	def checkPossibility(self, nums: list) -> bool:
		if len(nums)<=2:
			return True
		for i in range(len(nums)):
			copyofNums=[]
			for j in range(len(nums)):
				if j==i:
					continue
				if len(copyofNums)==0 or nums[j]>=copyofNums[-1]:
					copyofNums.append(nums[j])
				if len(copyofNums)==len(nums)-1:
					return True
		return False
	'''

	'''法二：统筹规划三个数

	def checkPossibility(self, nums: list) -> bool:
		if len(nums) <= 2:
			return True
		count = 0
		for i in range(len(nums)):
			if i == 0 and nums[i] > nums[i + 1]:
				nums[i] = nums[i + 1]
				count += 1
				continue
			if i + 1 < len(nums) and nums[i] > nums[i + 1]:
				if nums[i - 1] <= nums[i + 1]:
					nums[i] = nums[i - 1]
				else:
					nums[i + 1] = nums[i]
				count += 1
		return count < 2
	'''

	'''法三：对于一个序列，如果存在索引p使A[p]>A[p+1]，那么p的个数就是要调整的次数'''
	def checkPossibility(self, nums: list) -> bool:
		if len(nums) <= 2:
			return True
		count=0
		for i in range(1,len(nums)):
			if nums[i-1]>nums[i]:
				count+=1
				if i-2>=0 and nums[i-2]>nums[i]:
					nums[i]=nums[i-1]
		return count<2


if __name__ == '__main__':
	# nums=[1]
	# nums=[1,2,3,4,5,6]
	# nums=[2,4,6,10,8,9]
	nums = [-1, 4, 2, 3]
	# nums=[4,2,3]
	# nums=[1,2,3,7,6,5]
	solution = Solution()
	print(solution.checkPossibility(nums))
